/* 8911106 302933981 Ofri Keidar */

/******************************************************************************
* Student Name: Ofri Keidar
* Exercise Name: Ex6
* File Description: Template class DeAmortArray. Represents a de-amortized array
* 				    for T objects. Holds 2 T arrays- "old" and "new". The new
* 				    array is 2 times bigger than the old one. Each time a new
* 				    element is added, it is added to the old array and
* 				    the 2 previous items are copied to the new array from the old
* 				    one. When the old one is full, the new one is half full- old
* 				    array's memory is freed and the pointer to its head is set
* 				    to point at new array's head, then a new array as twice as
* 				    new array's size is allocated and the pointer to new array
* 				    is set to its head.
******************************************************************************/


#ifndef DEAMORTARRAY_H_
#define DEAMORTARRAY_H_

#include <iostream>
using namespace std;

#define ARRAY_START 0 // used to initialize position in array to its start
#define INIT_ARRAY_SIZE 2 // used to initialize m_oldArray's size
#define FACTOR 2 // used to maintain the ratio between m_oldArray and m_newArray's size

template <typename T> class DeAmortArray {
private:

	int m_maxSize; // used to bound m_oldArray's size
	int m_addCounter; // used to count many element were added (= current size)
	int m_postionToCopy; // used as index of elements that should be copied from m_oldArray to m_newArray
	T* m_oldArray; // array of T objects, size n
	T* m_newArray; // array of T objects, size FACTOR*n

	/***************************************************************************************
	* function name: DeAmortArray(const DeAmortArray& arrayToCopy)
	* The Input: DeAmortArray object to be copied
	* The output: None
	* The Function operation: Empty implementation since DeAmortArray object should not be
	* 				          copied
	***************************************************************************************/
	DeAmortArray(const DeAmortArray& arrayToCopy) { }

public:
	/***************************************************************************************
	* function name: DeAmortArray()
	* The Input: None
	* The output: None
	* The Function operation: Initializes an array of T objects of size 2 and another array
	* 					      of size 4
	***************************************************************************************/
	DeAmortArray() {
		m_maxSize = INIT_ARRAY_SIZE; // initialize m_oldArray's maximal size
		m_postionToCopy = ARRAY_START; // initialize index elements to be copied
		m_addCounter = ARRAY_START; // initialize size counter as current size
		m_oldArray = new T[INIT_ARRAY_SIZE]; // allocate array of T*
		m_newArray = new T[FACTOR*INIT_ARRAY_SIZE]; // allocate array of T* with FACTOR times elements as m_oldArray
	}

	/***************************************************************************************
	* function name: ~DeAmortArray()
	* The Input: None
	* The output: None
	* The Function operation: Frees memory allocated to both arrays
	***************************************************************************************/
	~DeAmortArray() {
		// free allocated memory
		delete[] m_oldArray;
		delete[] m_newArray;
	}

	/***************************************************************************************
	* function name: void insert(T newData)
	* The Input: T object to be added
	* The output: None
	* The Function operation: If m_oldArray is full, it is deleted, m_oldArray is set as
	* 						  m_newArray and a new twice as big T array is allocated to m_newArray.
	* 						  newData is added to m_oldArray's first empty position from the
	* 						  left- m_addCounter counts how many time element have been added
	* 						  to m_oldArray and so helps finding this position.
	* 						  Then m_oldArray's 2 previous elements (if there are any) are copied
	* 						  to m_newArray- m_positionToCopy keeps the position that should
	* 						  be copied. At the end of the method, m_addCounter and m_positionToCopy
	* 						  are incremented
	***************************************************************************************/
	void insert(T newData) {

		// if m_oldArray is full, allocate a new array
		if (m_addCounter == m_maxSize) { // array if full if attempting adding at one position beyond its actual size

			m_newArray[m_maxSize-1] = m_oldArray[m_maxSize-1]; // copy last element
			delete[] m_oldArray; // free m_oldArray's memory
			m_oldArray = m_newArray; // new array is now the old one
			m_maxSize *= FACTOR; // double size bound
			m_newArray = new T[FACTOR*m_maxSize]; // the new array will be FACTOR times as its previous size
			m_postionToCopy = ARRAY_START; // new array allocated, start copying from start
		}

		m_oldArray[m_addCounter] = newData;//newElement; // add given data at m_oldArray's end

		// copy 2 previous elements from m_oldArray to m_newArray
		m_newArray[m_postionToCopy] = m_oldArray[m_postionToCopy];
		if (m_postionToCopy + 1 < m_maxSize) { // check if can add this element
			m_newArray[m_postionToCopy+1] = m_oldArray[m_postionToCopy+1];
		}

		++m_addCounter; // new element was added, increment count
		++m_postionToCopy; // at next insert, copy next 2 elements from m_oldArray to m_newArray

	}

	/***************************************************************************************
	* function name: T operator[](const int index) const
	* The Input: Index
	* The output: Element in position "index"
	* The Function operation: Returns element at given index from m_oldArray
	***************************************************************************************/
	T operator[](const int index) const {return m_oldArray[index];}

	/***************************************************************************************
	 * function name:  friend ostream& operator << (ostream &os, const DeAmortArray& arrayToPrint)
	 * The Input: Reference to DeAmortArray to be printed
	 * The output: ostream reference
	 * The Function operation: Prints each element in given array, from first to last
	 ***************************************************************************************/
	friend ostream& operator << (ostream &os, const DeAmortArray& arrayToPrint) {
		for (int i = 0; i < arrayToPrint.m_addCounter; ++i) {
			cout << arrayToPrint[i] << endl; // print m_oldArray's current element
		}
		return os;
	}
};


#endif
